package com.song.algorithm.bst;

/**
 * @desc: 二叉搜索树
 * @author: WUSONG
 * @date: 2018/10/18 0018下午 4:16
 */
public class BSTree<T extends Comparable<T>> {

    private BSTNode<T> root;



    public class BSTNode<T extends Comparable<T>>{
        T key;
        BSTNode<T> leftNode;
        BSTNode<T> rightNode;
        BSTNode<T> parentNode;

        public BSTNode(T key, BSTNode<T> leftNode, BSTNode<T> rightNode, BSTNode<T> parentNode) {
            this.key = key;
            this.leftNode = leftNode;
            this.rightNode = rightNode;
            this.parentNode = parentNode;
        }
    }

    /**
     * 添加节点
     * 注意：需要添加的节点跟“当前”进行对比，这个“当前”是根据while循环而变化的
     * @param tree
     * @param node
     */
    private void insert(BSTree<T> tree, BSTNode<T> node){
        BSTNode<T> prn = null;
        BSTNode<T> currentNode = tree.root;//从根节点开始
        //查找出node的插入位置，该位置即为node的parentNode（prn）
        while (currentNode != null){
            prn = currentNode;
            if (node.key.compareTo(currentNode.key) < 0){
                currentNode = currentNode.leftNode;
            }else {
                currentNode = currentNode.rightNode;
            }
        }
        node.parentNode = prn;
        if (prn == null){//原来的tree为初始化状态的时候，root为空（添加第一个节点的时候）
            tree.root = node;
        }else{
            if (node.key.compareTo(prn.key) < 0){
                prn.leftNode = node;
            }else {
                prn.rightNode = node;
            }
        }

    }

    public void insert(T key){
        BSTNode<T> node = new BSTNode<T>(key, null, null, null);
        this.insert(this, node);
    }

    /**
     * 前序遍历
     */
    public void preOrder(){
        preOrder(root);
    }

    private void preOrder(BSTNode<T> treeNode){
        if(treeNode != null) {
            System.out.print(treeNode.key + "  ");
            preOrder(treeNode.leftNode);
            preOrder(treeNode.rightNode);
        }
    }

    public void inOrder(){
        inOrder(root);
    }

    private void inOrder(BSTNode<T> node){
        if (node != null){
            inOrder(node.leftNode);
            System.out.print(node.key + "  ");
            inOrder(node.rightNode);
        }

    }

    public void postOrder(){
        postOrder(root);
    }

    private void postOrder(BSTNode<T> node){
        if (node != null) {
            postOrder(node.leftNode);
            postOrder(node.rightNode);
            System.out.print(node.key + "  ");
        }
    }

    private BSTNode<T> search(BSTNode<T> node, T key){
        if (node == null){
            return node;
        }
        if (key.compareTo(node.key) < 0){
            return search(node.leftNode, key);
        }else if ((key.compareTo(node.key) > 0 )){
            return search(node.rightNode, key);
        }else {
            return node;
        }
    }

    /**
     * 递归实现查找二叉树中键为key的节点
     */
    public BSTNode<T> search(T key){
        return search(root, key);
    }

    private BSTNode<T> iterativeSearch(BSTNode<T> node, T key){
        while (node != null){
            int cmt = key.compareTo(node.key);
            if (cmt < 0){
                node = node.leftNode;
            }else if (cmt > 0){
                node = node.rightNode;
            }else {
                return node;
            }

        }
        return node;
    }

    public BSTNode<T> iterativeSearch(T key){
        return iterativeSearch(root, key);
    }

    /**
     * 查找最大结点：返回tree为根结点的二叉树的最大结点。
     */
    private BSTNode<T> maximum(BSTNode<T> tree) {
        if (tree == null)
            return null;

        while(tree.rightNode != null)
            tree = tree.rightNode;
        return tree;
    }

    public T maximum() {
        BSTNode<T> p = maximum(root);
        if (p != null)
            return p.key;

        return null;
    }


}
